use std::ptr;
const BINOMIAL_HEAP_NULL: Option<ptr::NonNull<c_void>> = None;
#[derive(Debug, Clone, Copy, PartialEq)]
enum BinomialHeapType {
    BINOMIAL_HEAP_TYPE_MIN,
    BINOMIAL_HEAP_TYPE_MAX,
}
type BinomialHeapValue = *mut c_void;
type BinomialHeapCompareFunc = fn(BinomialHeapValue, BinomialHeapValue) -> i32;
#[repr(C)]
struct BinomialHeap {
    heap_type: BinomialHeapType,
    compare_func: BinomialHeapCompareFunc,
    num_values: u32,
    roots: *mut *mut BinomialTree,
    roots_length: u32,
}
#[repr(C)]
struct BinomialTree {
    value: BinomialHeapValue,
    order: u16,
    refcount: u16,
    subtrees: *mut *mut BinomialTree,
}
fn binomial_heap_cmp(
    heap: &mut BinomialHeap,
    data1: BinomialHeapValue,
    data2: BinomialHeapValue,
) -> i32 {
    match heap.heap_type {
        BinomialHeapType::BINOMIAL_HEAP_TYPE_MIN => (heap.compare_func)(data1, data2),
        _ => -(heap.compare_func)(data1, data2),
    }
}
fn binomial_tree_ref(tree: *mut BinomialTree) {
    if !tree.is_null() {
        unsafe {
            (*tree).refcount += 1;
        }
    }
}
fn binomial_tree_unref(tree: *mut BinomialTree) {
    if tree.is_null() {
        return;
    }
    unsafe {
        (*tree).refcount -= 1;
        if (*tree).refcount == 0 {
            for i in 0..(*tree).order {
                binomial_tree_unref(*(*tree).subtrees.add(i));
            }
            libc::free((*tree).subtrees as *mut libc::c_void);
            libc::free(tree as *mut libc::c_void);
        }
    }
}
#[no_mangle]
fn binomial_tree_merge(
    heap: *mut BinomialHeap,
    tree1: *mut BinomialTree,
    tree2: *mut BinomialTree,
) -> *mut BinomialTree {
    let mut new_tree: *mut BinomialTree;
    let mut tmp: *mut BinomialTree;
    let mut i: i32;
    unsafe {
        if binomial_heap_cmp(heap, (*tree1).value, (*tree2).value) > 0 {
            tmp = tree1;
            tree1 = tree2;
            tree2 = tmp;
        }
        new_tree = alloc::alloc(Layout::new::<BinomialTree>()) as *mut BinomialTree;
        if new_tree.is_null() {
            return ptr::null_mut();
        }
        (*new_tree).refcount = 0;
        (*new_tree).order = ((*tree1).order + 1) as u16;
        (*new_tree).value = (*tree1).value;
        (*new_tree).subtrees =
            alloc::alloc(Layout::array::<*mut BinomialTree>((*new_tree).order as usize).unwrap())
                as *mut *mut BinomialTree;
        if (*new_tree).subtrees.is_null() {
            alloc::dealloc(new_tree as *mut u8, Layout::new::<BinomialTree>());
            return ptr::null_mut();
        }
        ptr::copy_nonoverlapping(
            (*tree1).subtrees,
            (*new_tree).subtrees,
            (*tree1).order as usize,
        );
        *(*new_tree).subtrees.add((*new_tree).order as usize - 1) = tree2;
        for i in 0..(*new_tree).order {
            binomial_tree_ref(*(*new_tree).subtrees.add(i as usize));
        }
    }
    new_tree
}
fn binomial_heap_merge_undo(new_roots: *mut *mut BinomialTree, count: u32) {
    for i in 0..=count {
        binomial_tree_unref(*new_roots.add(i as usize));
    }
    free(new_roots as *mut libc::c_void);
}
fn binomial_heap_merge(heap: &mut BinomialHeap, other: &BinomialHeap) -> i32 {
    let mut new_roots: Vec<Option<&mut BinomialTree>> = Vec::new();
    let mut new_roots_length: u32 = 0;
    let mut vals = vec![None, None, None];
    let mut num_vals: u32;
    let mut carry: Option<&mut BinomialTree> = None;
    let mut new_carry: Option<&mut BinomialTree> = None;
    let max: u32;
    max = if heap.roots_length > other.roots_length {
        heap.roots_length + 1
    } else {
        other.roots_length + 1
    };
    new_roots.resize(max as usize, None);
    for i in 0..max {
        num_vals = 0;
        if i < heap.roots_length && heap.roots[i as usize].is_some() {
            vals[num_vals as usize] = heap.roots[i as usize];
            num_vals += 1;
        }
        if i < other.roots_length && other.roots[i as usize].is_some() {
            vals[num_vals as usize] = other.roots[i as usize];
            num_vals += 1;
        }
        if carry.is_some() {
            vals[num_vals as usize] = carry.clone();
            num_vals += 1;
        }
        if num_vals % 2 != 0 {
            new_roots[i as usize] = vals[(num_vals - 1) as usize].take();
            binomial_tree_ref(new_roots[i as usize].as_mut().unwrap());
            new_roots_length = i + 1;
        } else {
            new_roots[i as usize] = None;
        }
        if num_vals % 2 == 0 {
            new_carry = binomial_tree_merge(heap, vals[0].as_mut(), vals[1].as_mut());
            if new_carry.is_none() {
                binomial_heap_merge_undo(&mut new_roots, i);
                binomial_tree_unref(carry.clone());
                return 0;
            }
        } else {
            new_carry = None;
        }
        binomial_tree_unref(carry.clone());
        carry = new_carry.clone();
        binomial_tree_ref(carry.clone());
    }
    for i in 0..heap.roots_length {
        if heap.roots[i as usize].is_some() {
            binomial_tree_unref(heap.roots[i as usize].clone());
        }
    }
    heap.roots = new_roots;
    heap.roots_length = new_roots_length;
    1
}
fn binomial_heap_new(
    heap_type: BinomialHeapType,
    compare_func: BinomialHeapCompareFunc,
) -> *mut BinomialHeap {
    unsafe {
        let new_heap = libc::calloc(1, mem::size_of::<BinomialHeap>()) as *mut BinomialHeap;
        if new_heap.is_null() {
            return ptr::null_mut();
        }
        (*new_heap).heap_type = heap_type;
        (*new_heap).compare_func = compare_func;
        new_heap
    }
}
fn binomial_heap_free(heap: *mut BinomialHeap) {
    unsafe {
        for i in 0..(*heap).roots_length {
            binomial_tree_unref(*(*heap).roots.offset(i as isize));
        }
        free((*heap).roots as *mut libc::c_void);
        free(heap as *mut libc::c_void);
    }
}
fn binomial_heap_insert(heap: &mut BinomialHeap, value: BinomialHeapValue) -> i32 {
    let mut fake_heap = BinomialHeap {
        heap_type: heap.heap_type,
        compare_func: heap.compare_func,
        num_values: 1,
        roots: &mut Vec::new(),
        roots_length: 1,
    };
    let mut new_tree = Box::new(BinomialTree {
        value,
        order: 0,
        refcount: 1,
        subtrees: std::ptr::null_mut(),
    });
    fake_heap.roots.push(&mut new_tree);
    let result = binomial_heap_merge(heap, &mut fake_heap);
    if result != 0 {
        heap.num_values += 1;
    }
    binomial_tree_unref(&mut new_tree);
    result
}
fn binomial_heap_pop(heap: &mut BinomialHeap) -> BinomialHeapValue {
    let mut least_tree: *mut BinomialTree;
    let mut fake_heap: BinomialHeap;
    let mut result: BinomialHeapValue;
    let mut i: u32;
    let mut least_index: u32;
    if heap.num_values == 0 {
        return BINOMIAL_HEAP_NULL;
    }
    least_index = u32::MAX;
    for i in 0..heap.roots_length {
        if heap.roots[i as usize].is_null() {
            continue;
        }
        if least_index == u32::MAX
            || binomial_heap_cmp(
                heap,
                (*heap.roots[i as usize]).value,
                (*heap.roots[least_index as usize]).value,
            ) < 0
        {
            least_index = i;
        }
    }
    least_tree = heap.roots[least_index as usize];
    heap.roots[least_index as usize] = std::ptr::null_mut();
    fake_heap.heap_type = heap.heap_type;
    fake_heap.compare_func = heap.compare_func;
    fake_heap.roots = (*least_tree).subtrees;
    fake_heap.roots_length = (*least_tree).order;
    if binomial_heap_merge(heap, &fake_heap) {
        result = (*least_tree).value;
        binomial_tree_unref(least_tree);
        heap.num_values -= 1;
        return result;
    } else {
        heap.roots[least_index as usize] = least_tree;
        return BINOMIAL_HEAP_NULL;
    }
}
fn binomial_heap_num_entries(heap: &BinomialHeap) -> u32 {
    heap.num_values
}

